#include<cstdio>
const int MAXN=1005;

long long x[MAXN];
long long a[MAXN],b[MAXN];
long long dp[MAXN][MAXN];

int q[MAXN],h,t;

double slop(int i,int j,int k)
{return (1.0*(dp[i][k]+(a[k]*a[k]+b[k])/2.0)-(dp[i][j]+(a[j]*a[j]+b[j])/2.0))/(1.0*(a[k]-a[j]));}

int main()
{
	int n,m;
	for(;;)
	{
		scanf("%d%d",&n,&m);
		if(n==0&&m==0)
			break;
		for(int i=1;i<=n;i++)
		{
			scanf("%I64d",&x[i]);
			a[i]=a[i-1]+x[i];
			b[i]=b[i-1]+x[i]*x[i];
		}
		
		for(int j=0;j<=n;j++)
			dp[0][j]=(a[j]*a[j]-b[j])/2;
		for(int i=1;i<=m;i++)
		{
			q[h=t=1]=i;
			for(int j=i+1;j<=n;j++)
			{
				while(h<t&&slop(i-1,q[h],q[h+1])<a[j])
					h++;
				dp[i][j]=dp[i-1][q[h]]+((a[j]-a[q[h]])*(a[j]-a[q[h]])-(b[j]-b[q[h]]))/2;
				//printf("dp[%d][%d]->dp[%d][%d]=%I64d\n",i-1,q[h],i,j,dp[i][j]);
				while(h<t&&slop(i-1,q[t-1],q[t])>slop(i-1,q[t],j))
					t--;
				q[++t]=j;
			}
		}
		
		printf("%I64d\n",dp[m][n]);
	}
	
	return 0;
}
